package algorithm.leetcode;

/**
 * 最长回文子串
 * 中心扩展法
 */
public class LongestPalindrome {

    /**
     * 中心扩展法
     * 1. 求得回文字符串的长度
     * 2. 计算start和end的值
     * 3. 如果这个值比现有的值大，那么就取新的值
     * @param str
     * @return
     */
    public String longestPalindrome(String str) {
        if(str.length() == 1) {
            return str;
        }

        if(str.length() == 2 && (str.charAt(0) == str.charAt(1))) {
            return str;
        }
        int start = 0;
        int end = 0;

        for(int i=0; i<str.length(); i++) {
            int len1 = longestStr(str, i, i);
            int len2 = longestStr(str, i, i+1);
            int len = Math.max(len1, len2);
            if(len > (end -start)) {
                start = i - (len-1)/2;
                end = i + len/2;
            }
        }

        return str.substring(start, end + 1);
    }

    private int longestStr(String str, int left, int right) {
        while( left>= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
            left = left-1;
            right = right + 1;
        }
        return right - left - 1;
    }

    public static void main(String[] args) {
        System.out.println(new LongestPalindrome().longestPalindrome("ccc"));
    }
}
